package mht.leetCode.primary.dp;

public class Solution {

    /**
     * 【爬楼梯】
     *
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     *
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶
     * 2.  2 阶
     * 示例 2：
     *
     * 输入： 3
     * 输出： 3
     * 解释： 有三种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶 + 1 阶
     * 2.  1 阶 + 2 阶
     * 3.  2 阶 + 1 阶
     *
     */
    public int climbStairsByDP(int n) {
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;

        int res = 0;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
            res = dp[i];
        }
        return res;
    }

    // 斐波那契解法（递归法)
    public int climbStairsOne(int n) {
        if (n == 0) {
            return 1;
        }

        if (n == 1) {
            return 1;
        }

        return climbStairsOne(n-1) + climbStairsOne(n-2);
    }

    // 斐波那契解法（非递归法)
    public int climbStairsAnother(int n) {
        /**
         * 思路：
         * 台阶     步数
         * 1        1
         * 2        2
         * 3        3
         * 4        5
         * 5        8
         */

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int sum = 0;
        int first;
        int second;
        first = 1;
        second = 2;

        for (int i = 2; i < n; i++) {
            sum = first + second;
            first = second;
            second = sum;
        }

        return sum;
    }

    /**
     * 【最大子序和】
     *
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 示例:
     *
     * 输入: [-2,1,-3,4,-1,2,1,-5,4],
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     *
     */
    public int maxSubArray(int[] nums) {

        // 思路：动态规划：很简单，定义一个数组，dp[]，dp[i]以第i个元素为结尾的一段最大子序和。
        // 求dp[i]时，假设前面dp[0]~dp[i-1]都已经求出来了，dp[i-1]表示的是以i-1为结尾的最大子序和，
        // 若dp[i-1]小于0，则dp[i]加上前面的任意长度的序列和都会小于不加前面的序列（即自己本身一个元素是以自己为结尾的最大自序和）。
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int sum = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (res > 0) {
                res = res + nums[i];
            } else {
                res = nums[i];
            }

            if (res > sum) {
                sum = res;
            }
        }
        return sum;
    }

    /**
     * 【打家劫舍】
     *
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     *
     * 示例 1:
     *
     * 输入: [1,2,3,1]
     * 输出: 4
     * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 2:
     *
     * 输入: [2,7,9,3,1]
     * 输出: 12
     * 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     */
    public int rob(int[] nums) {

        // 思路：这是一个求最优解的问题，使用动态规划。
        // 使用dp[i]表示第i间房屋能够偷窃到的最高金额，nums[i]表示第i间房屋存放的金额。
        // 对于第n间房屋，能够偷窃到的最高金额是dp[i-1]或dp[i-2]+nums[i]。
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int pre1 = 0;
        int pre2 = 0;
        int cur;

        for (int num : nums) {

            cur = Math.max(pre2 + num, pre1);

            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}
